Cao Trừng sinh năm 521, lúc đó cha ông là Cao Hoan vẫn là một người chạy dịch trạm chuyển văn thư giữa kinh đô Lạc Dương và cố độ Bình Thành (平城, nay thuộc Đại Đồng, Sơn Tây) của Bắc Ngụy. Mẹ ông là Lâu Chiêu Quân, bà xuất thân trong một gia đình giàu có, song gia đình Cao Hoan lại nghèo túng. Năm 525, Cao Hoan tham gia vào cuộc khởi nghĩa nông dân do Đỗ Lạc Chu lãnh đạo. Sau đó, Cao Hoan cho rằng Đỗ Lạc Chu không phải là một lãnh tụ thành công nên đã tìm cách đào tẩu khỏi doanh trại của Đỗ Lạc Chu cùng với các cộng sự Úy Cảnh (尉景), Đoàn Vinh (段榮), và Thái Tuyển (蔡雋). Lâu thị cùng Cao Trừng và một người con gái cũng chạy trốn bằng cách cưỡi một con bò. Trong cuộc đào tẩu này, Cao Trừng đã nhiều lần rơi khỏi lưng bò, vì thế Cao Hoan từng tính đến chuyện dùng tên giết chết Cao Trừng, song Đoàn Vinh đã cứu giúp ông. Đến năm 531, khi đã là một tướng của Bắc Ngụy, Cao Hoan nổi dậy chống lại gia tộc Nhĩ Chu Vinh vốn kiểm soát nền chính trị của đế quốc. Khi một lãnh đạo khởi nghĩa nông dân, cũng là một họ hàng rất xa của Hoang Hoan, là Cao Ngao Tào (高敖曹) từ chối đi theo Cao Hoan, Cao Hoan đã cử Cao Trừng đến viếng thăm Cao Ngao Tào và thể hiện sự kính trọng với người này, thuyết phục Cao Ngao Tào về sự thành thật của Cao Hoan.